package cn.edu.xjtu.work.isListPalindrome;

/**
 * 回文链表
 * 
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 */
import java.util.Stack;

import cn.edu.xjtu.Util.ListNode.ListNode;
import cn.edu.xjtu.Util.ListNode.ListNodeUtil;

public class Solution {
  public static void main(String[] args) {
    ListNode head = new ListNode(1);
    ListNode temp = head;
    temp.next = new ListNode(2);
    temp = temp.next;
    temp.next = new ListNode(3);
    temp = temp.next;
    temp.next = new ListNode(3);
    temp = temp.next;
    temp.next = new ListNode(1);
    ListNodeUtil.print(head);
    System.out.println(isPalindrome(head));
  }

  public static boolean isPalindrome(ListNode head) {
    Stack<Integer> s = new Stack<>();
    ListNode l = head;
    while (l != null) {
      s.push(l.val);
      l = l.next;
    }
    int len = s.size();
    l = head;
    for (int i = 0; i < len / 2; i++) {
      if (l.val != s.pop()) {
        return false;
      }
      l = l.next;
    }
    return true;
  }
}
